package com.lft.graph02.traverse_graph;

import java.lang.reflect.Array;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 无向图的实现——邻接矩阵
 */
public class GraphAdjacencyMatrix<E> implements GraphInterface<E> {
	/**
	 * 存储图的顶点的一维数组
	 */
	private E[] vertexs;
	
	/**
	 * 存储图的边的二维数组
	 */
	private int[][] edges;
	
	/**
	 * 顶点的实际数量
	 */
	private int numOfVertexs;
	
	/**
	 * 顶点的最大数量
	 */
	private int maxNumOfVertexs;
	
	/**
	 * 判断顶点是否被反问过。 true：访问过；false：未访问过。
	 */
	private boolean[] visited;
	
	/**
	 * 构造器，初始化顶点数组和边数组。
	 * @param maxNumOfVertexs
	 * @param type
	 */
	public GraphAdjacencyMatrix(int maxNumOfVertexs, Class<E> type) {
		this.maxNumOfVertexs = maxNumOfVertexs;
		edges = new int[maxNumOfVertexs][maxNumOfVertexs];
		vertexs = (E[]) Array.newInstance(type, maxNumOfVertexs);
	}
	
	/**
	 * 获取顶点的个数。
	 * @return
	 */
	@Override
	public int getNumOfVertex() {
		return numOfVertexs;
	}
	
	/**
	 * 插入顶点
	 * @param v
	 * @return
	 */
	@Override
	public boolean insertVertex(E v) {
		if (numOfVertexs >= maxNumOfVertexs) {
			return false;
		}
		vertexs[numOfVertexs++] = v;
		return true;
	}
	
	/**
	 * 删除顶点
	 * @param v
	 * @return
	 */
	@Override
	public boolean deleteVertex(E v) {
		// 遍历每个顶点
		for (int i = 0; i < numOfVertexs; i++) {
			// 当前顶点跟要删除的顶点相等。
			if (vertexs[i].equals(v)) {
				// 遍历将当前顶点用后面的顶点替换删除。
				for (int j = i; j < numOfVertexs - 1; j++) {
					// 遍历顶点数组，将后面的往前移动，替换掉要删除的顶点。
					vertexs[j] = vertexs[j + 1];
				}
				// 将数组末尾置空。
				vertexs[numOfVertexs - 1] = null;
				// 遍历列，修改边
				for (int col = i; col < numOfVertexs - 1; col++) {
					for (int row = 0; row < numOfVertexs; row++) {
						edges[col][row] = edges[col + 1][row];
					}
				}
				// 遍历行，修改边
				for (int row = i; row < numOfVertexs - 1; row++) {
					for (int col = 0; col < numOfVertexs; col++) {
						edges[col][row] = edges[col][row + 1];
					}
				}
				// 顶点数量减1
				numOfVertexs--;
				return true;
			}
		}
		return false;
	}
	
	/**
	 * 定位顶点的位置
	 * @param v 要查找的顶点。
	 * @return -1 未找到。其他值就是顶点的索引。
	 */
	@Override
	public int indexOfVertex(E v) {
		for (int i = 0; i < numOfVertexs; i++) {
			if (vertexs[i].equals(v)) {
				return i;
			}
		}
		return -1;
	}
	
	/**
	 * 查找指定位置的顶点的值
	 * @param vertexIndex
	 * @return
	 */
	@Override
	public E valueOfVertex(int vertexIndex) {
		if (vertexIndex < 0 || vertexIndex >= numOfVertexs) {
			return null;
		}
		return vertexs[vertexIndex];
	}
	
	/**
	 * 插入边
	 * @param vertexIndex1 顶点1索引
	 * @param vertexIndex2 顶点2索引
	 * @param weight       权重 1表示连接。0表示不通。
	 * @return 插入成功返回 true;
	 */
	@Override
	public boolean insertEdge(int vertexIndex1, int vertexIndex2, int weight) {
		if (vertexIndex1 < 0 || vertexIndex1 >= numOfVertexs || vertexIndex2 < 0 || vertexIndex2 >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		edges[vertexIndex1][vertexIndex2] = weight;
		edges[vertexIndex2][vertexIndex1] = weight;
		return true;
	}
	
	/**
	 * 删除边
	 * @param vertexIndex1 顶点1索引
	 * @param vertexIndex2 顶点2索引
	 * @return 删除成功 返回true.
	 */
	@Override
	public boolean deleteEdge(int vertexIndex1, int vertexIndex2) {
		if (vertexIndex1 < 0 || vertexIndex1 >= numOfVertexs || vertexIndex2 < 0 || vertexIndex2 >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		edges[vertexIndex1][vertexIndex2] = 0;
		edges[vertexIndex2][vertexIndex1] = 0;
		return true;
	}
	
	/**
	 * 返回 vertexIndex 顶点的第一个邻接顶点的索引
	 * @param vertexIndex
	 * @return
	 */
	@Override
	public int getFirstAdjacencyVertexIndex(int vertexIndex) {
		for (int i = 0; i < numOfVertexs; i++) {
			// 边的权值不是0和最大值。就说明这两个顶点存在边。
			if (edges[vertexIndex][i] > 0 && edges[vertexIndex][i] < Integer.MAX_VALUE) {
				// 返回第一个边的索引。
				return i;
			}
		}
		return -1;
	}
	
	/**
	 * 返回 vertexIndex1 顶点的 vertexIndex2 邻接顶点后一个邻接顶点的索引
	 * @param vertexIndex1
	 * @param vertexIndex2
	 * @return
	 */
	@Override
	public int getNextAdjacencyVertexIndex(int vertexIndex1, int vertexIndex2) {
		for (int i = vertexIndex2 + 1; i < numOfVertexs; i++) {
			if (edges[vertexIndex1][i] > 0 && edges[vertexIndex1][i] < Integer.MAX_VALUE) {
				return i;
			}
		}
		return -1;
	}
	
	/**
	 * 查找顶点1与顶点2边的权值
	 * @param vertexIndex1 顶点1索引
	 * @param vertexIndex2 顶点2索引
	 * @return 权值
	 */
	@Override
	public int getEdge(int vertexIndex1, int vertexIndex2) {
		if (vertexIndex1 < 0 || vertexIndex1 >= numOfVertexs || vertexIndex2 < 0 || vertexIndex2 >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		return edges[vertexIndex1][vertexIndex2];
	}
	
	/**
	 * 邻接矩阵-深度优先搜索遍历——基于栈实现
	 * @param vertexIndex 顶点索引
	 * @return
	 */
	@Override
	public String depthFirstSearchByStack(int vertexIndex) {
		if (vertexIndex < 0 || vertexIndex > numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		// 重新初始化访问标志
		visited = new boolean[numOfVertexs];
		// 创建 StringBuilder 对象，用于遍历输出打印。
		StringBuilder sb = new StringBuilder();
		
		// 创建一个栈，入栈出栈的是索引。
		Stack<Integer> stack = new Stack<>();
		// 先将当前顶点的索引压入栈中。
		stack.push(vertexIndex);
		// 将当前索引的访问标记设置为 true
		visited[vertexIndex] = true;
		// 只要栈不为空，循环遍历
		while (!stack.isEmpty()) {
			// 弹出栈顶索引。赋值给 vertexIndex
			vertexIndex = stack.pop();
			// 将 vertexIndex 索引下的顶点的值拼接到 sb 中。
			sb.append(vertexs[vertexIndex] + ",");
			// 从最后一个顶点开始 循环遍历
			for (int i = numOfVertexs - 1; i >= 0; i--) {
				// 如果 vertexIndex 顶点 和 i 顶点 连通。且权值是一个正常整数。且顶点访问标记是未访问。
				if (edges[vertexIndex][i] != 0 && edges[vertexIndex][i] != Integer.MAX_VALUE && !visited[i]) {
					// 将 i 索引压入栈中。
					stack.push(i);
					// 将 i 索引的顶点标记为 已访问。
					visited[i] = true;
				}
			}
		}
		// sb 长度大于0，将 sb 从头到尾返回，否则返回 null
		return sb.length() > 0 ? sb.substring(0, sb.length() - 1) : null;
	}
	
	/**
	 * 邻接矩阵-深度优先搜索遍历——基于递归
	 * @param vertexIndex 顶点索引
	 * @return
	 */
	@Override
	public String depthFirstSearchByRecursion(int vertexIndex) {
		if (vertexIndex < 0 || vertexIndex >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		// 重新初始化访问标志
		visited = new boolean[numOfVertexs];
		StringBuilder sb = new StringBuilder();
		// 先将当前顶点遍历输出。
		depthFirstSearchByRecursion(vertexIndex, sb);
		// 如果图是非连通图，那么我们这里还需要对每个顶点遍历一次，保证全部顶点都被访问到了。
		for (int i = 0; i < numOfVertexs; i++) {
			// 如果有顶点没有被访问过。调用递归方法访问一下。
			if (!visited[i]) {
				depthFirstSearchByRecursion(i, sb);
			}
		}
		return sb.length() > 0 ? sb.substring(0, sb.length() - 1) : null;
	}
	
	/**
	 * 邻接矩阵-用于递归DFS遍历
	 * @param vertexIndex
	 * @param sb
	 * @return
	 */
	private void depthFirstSearchByRecursion(int vertexIndex, StringBuilder sb) {
		if (vertexIndex < 0 || vertexIndex >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		sb.append(vertexs[vertexIndex] + ",");
		visited[vertexIndex] = true;
		// 查找 vertexIndex 顶点的第一个邻接顶点
		int adjacencyVertexIndex = getFirstAdjacencyVertexIndex(vertexIndex);
		// 找到邻接顶点
		while (adjacencyVertexIndex != -1) {
			// 并且 firstAdjacencyVertexIndex 顶点没有被访问过。
			if (!visited[adjacencyVertexIndex]) {
				// 递归进行访问。
				depthFirstSearchByRecursion(adjacencyVertexIndex, sb);
			}
			// 该顶点被访问过了。
			else {
				// 就查找 adjacencyVertexIndex 的下一个邻接顶点的索引。（深度优先就体现在这里。一直是找 index 后面的能直接连通的顶点）
				adjacencyVertexIndex = getNextAdjacencyVertexIndex(vertexIndex, adjacencyVertexIndex);
			}
		}
	}
	
	/**
	 * 邻接矩阵-广度优先搜索遍历——基于队列实现
	 * @param vertexIndex 顶点索引
	 * @return
	 */
	@Override
	public String breadFirstSearchByQueue(int vertexIndex) {
		if (vertexIndex < 0 || vertexIndex >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		// 重新初始化访问标志
		visited = new boolean[numOfVertexs];
		StringBuilder sb = new StringBuilder();
		// 创建一个队列。
		Queue<Integer> queue = new LinkedList<>();
		// 调用方法对当前的顶点进行广度优先遍历
		breadFirstSearchByQueue(vertexIndex, sb, queue);
		
		// 再将每个顶点遍历一次。以防有顶点没有边的情况
		for (int i = 0; i < numOfVertexs; i++) {
			if (!visited[i]) {
				breadFirstSearchByQueue(i, sb, queue);
			}
		}
		// 返回遍历到的顶点数据
		return sb.length() > 0 ? sb.substring(0, sb.length() - 1) : null;
	}
	
	/**
	 * 邻接矩阵-真实的广度优先搜索遍历方法
	 * @param vertexIndex
	 * @param sb
	 * @param queue
	 * @return
	 */
	private void breadFirstSearchByQueue(int vertexIndex, StringBuilder sb, Queue<Integer> queue) {
		if (vertexIndex < 0 || vertexIndex >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		// 将当前节点的信息保存
		sb.append(valueOfVertex(vertexIndex) + ",");
		// 设置当前顶点访问标志为true
		visited[vertexIndex] = true;
		// 添加当前索引到队列
		queue.offer(vertexIndex);
		// 队列不为空，一直遍历。
		while (!queue.isEmpty()) {
			// 出队列的值赋值给 vertexIndex
			vertexIndex = queue.poll();
			// 获取这个索引的第一个邻接顶点的下标。
			int adjacencyVertexIndex = getFirstAdjacencyVertexIndex(vertexIndex);
			// 如果 index 顶点的这个邻接顶点 adjacencyVertexIndex 索引不等于-1，说明他两有边
			while (adjacencyVertexIndex != -1) {
				// 判断当前顶点是否访问过。
				if (!visited[adjacencyVertexIndex]) {
					// 如果没有访问过 将当前顶点的数据添加到 sb 中。
					sb.append(valueOfVertex(adjacencyVertexIndex) + ",");
					// 将该索引下的顶点访问标志设置为 true.
					visited[adjacencyVertexIndex] = true;
					// 并将当前 adjacencyVertexIndex 索引入队列。
					queue.offer(adjacencyVertexIndex);
				}
				// 如果访问了。就查找 vertexIndex 的下一个邻接顶点的索引。（广度优先就体现在这里。一直是在找 vertexIndex 能直接连通的顶点）
				adjacencyVertexIndex = getNextAdjacencyVertexIndex(vertexIndex, adjacencyVertexIndex);
			}
		}
	}
	
	/**
	 * 打印邻接矩阵
	 */
	@Override
	public void displayGraph() {
		for (int i = 0; i < numOfVertexs; i++) {
			for (int j = 0; j < numOfVertexs; j++) {
				System.out.print(edges[i][j] + "\t");
			}
			System.out.println();
		}
	}
}